package geekstudy.week6;

import java.util.List;

/**
 * 120. 三角形最小路径和
 * https://leetcode-cn.com/problems/triangle/submissions/
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：2 ms, 在所有 Java 提交中击败了95.64% 的用户
 * 内存消耗：38.4 MB, 在所有 Java 提交中击败了64.97% 的用户
 */
public class Week6Triangle {

    public int minimumTotal(List<List<Integer>> triangle) {
        //记录矩阵的行数
        int rowNum = triangle.size();

        //记录最后一行数组的值（行数和列数相等）
        int[] cache = new int[rowNum];
        for(int size = 0; size < rowNum ; size++){
            cache[size] = triangle.get(rowNum -1).get(size);
        }

        //从倒数第二行数组开始遍历
        for(int size = rowNum -2; size>= 0; size--){
            for(int n = 0; n <= size; n++){
                cache[n] = Math.min(cache[n], cache[n+1])
                        + triangle.get(size).get(n);
            }
        }
        return cache[0];
    }


}
